/*
 * @Author: liusheng
 * @Date: 2022-07-02 18:53:29
 * @LastEditors: liusheng
 * @LastEditTime: 2022-07-02 19:11:52
 * @Description: 剑指 Offer II 094. 最少回文分割
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 094. 最少回文分割
给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的 最少分割次数 。

 

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：

输入：s = "a"
输出：0
示例 3：

输入：s = "ab"
输出：1
 

提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成
 

注意：本题与主站 132 题相同： https://leetcode-cn.com/problems/palindrome-partitioning-ii/

通过次数7,470  提交次数12,833
 */

#include "header.h"

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<int>> isPalindrome(n,vector<int>(n,true));

        /*
        s[i] to s[j] Palindrome check,status transfer
        */
        for (int i = n - 1; i >=0; --i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                isPalindrome[i][j] = isPalindrome[i+1][j-1] && (s[i] == s[j]);
            }
        }

        /*
        s[0..i] minCut
        */
        vector<int> dp(n,INT_MAX);
        for (int i = 0; i < n; ++i)
        {
            if(isPalindrome[0][i])
            {
                dp[i] = 0;
            }
            else
            {
                for (int j = 0; j < i; ++j)
                {
                    if (isPalindrome[j + 1][i])
                    {
                        dp[i] = min(dp[i],dp[j] + 1);
                    }
                }
            }
        }

        return dp[n-1];
    }
};
